
/**
 * 堆排序的过程为：
 * 1. 创建一个大顶锥
 * 2. 把堆顶元素（最大值）和堆尾元素互换
 * 3. 缩小堆的尺寸，并调用函数从新的堆顶元素进行堆调整
 * 4. 重复步骤2，知道堆的尺寸为1.此时为升序排列
 */

public class heapSort{

	private int heapsize;

	/**
	 * 分类： 内部比较排序
	 * 数据结构： 数组
	 * 最差时间复杂度： O(nlogn)
	 * 最优时间复杂度： O(nlogn)
	 * 平均时间复杂度： O(nlogn)
	 * 所需辅助空间：   O(1)
	 * 稳定性：         不稳定
	 * [sort description]： 堆排序，每次将大顶锥的堆顶元素放在数组末尾，并减小大顶锥的size
	 * @param array [description]
	 */
	public void sort(int [] array){
		int len = array.length;
		heapsize = len;
		for(int i=len/2-1;i>0;i--){  //建堆的过程
			heapAdjust(array,i);
		}
		for (int i=len-1; i>=1; i--) {
			exchange(array,0,i);      //交换堆顶元素和数组末尾的元素的值
			heapsize --;              //堆的大小减1
			heapAdjust(array,0);      //从堆顶开始调整
		}
	}

	/**
	 * 对于第index个节点，比较其左右子节点，如果有子节点的值大于index节点的值，则记下最大值的索引为maxIndex
	 * 如果maxIndex  != index，则认为做出了调整，并递归调用该函数，最maxIndex节点进行调整
	 * [heapAdjust description]: 堆的自动调整
	 * @param array [description]
	 * @param index [description]
	 */
	void heapAdjust(int array,int index){
		int left = 2*index+1;
		int right = 2*index+2;
		int maxIndex = index;
		if(left < heapsize && array[left] > array[maxIndex]){
			maxIndex = left;
		}
		if(right < heapsize && array[right] > array[maxIndex]){
			maxIndex = right;
		}
		if(maxIndex != index){
			exchange(array,index,maxIndex);
			heapAdjust(array,maxIndex);
		}
	}

	/**
	 * 交换两个索引对应的节点的值
	 * [exchange description]
	 * @param array  [description]
	 * @param first  [description]
	 * @param second [description]
	 */
	void exchange(int array,int first, int second){
		array[first] = array[first] ^ array[second];
		array[second] = array[first] ^ array[second];
		array[first] = array[first] ^ array[second];
	}
}